#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//以下均为力扣网所写代码
////二叉树的前序遍历
//struct TreeNode {
//	int val;
//	struct TreeNode* left;
//	struct TreeNode* right;
//	
//};
//void prevorder(struct TreeNode* root, int* a, int* i)
//{
//
//    if (root == NULL)
//    {
//        return;
//    }
//    a[(*i)++] = root->val;
//    prevorder(root->left, a, i);
//    prevorder(root->right, a, i);
//}
//int TreeSize(struct TreeNode* root)
//{
//    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
//int* preorderTraversal(struct TreeNode* root, int* returnsize) {
//    *returnsize = TreeSize(root);
//    int* ret = (int*)malloc(sizeof(int) * (*returnsize));
//    int i = 0;
//    prevorder(root, ret, &i);
//    return ret;
//}
//int main()
//{
//    struct TreeNode* root;
//    int size = 0;
//    preorderTraversal(root, size);
//}
//给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同(相同的树)
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
    {
        return true;
    }
    if (p == NULL || q == NULL)
    {
        return false;
    }
    if (p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
int main()
{
    struct TreeNode* p;
    struct TreeNode* q;
    bool i = isSameTree(p, q);
    return 0;
}

//对称二叉树
//先比较根，在第二层比较左右子树，在第三层以二层的根为节点拿左子树的左子树跟右子树的右子树比；
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
    {
        return true;
    }
    if (p == NULL || q == NULL)
    {
        return false;
    }
    if (p->val != q->val)
    {
        return false;
    }
    return _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {
    return  _isSymmetric(root->left, root->right) && _isSymmetric(root->right, root->left);
}
//给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //两个都为空
    if (p == NULL && q == NULL)
    {
        return true;
    }
    //一个为空，一个不为空
    if (p == NULL || q == NULL)
    {
        return false;
    }
    if (p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
//找到与子根相同的节点
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL)
    {
        return false;
    }
    if (root->val == subRoot->val && isSameTree(root, subRoot))
    {
        return true;
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
//编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 
//其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果

#include <stdio.h>
#include<stdlib.h>

typedef struct BinTreenode {
    char val;
    struct BinTreenode* left;
    struct BinTreenode* right;
}BTnode;
BTnode* CreatTree(char* a, int* pi)
{
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;

    }
    BTnode* root = (BTnode*)malloc(sizeof(BTnode));
    root->val = a[(*pi)++];
    root->left = CreatTree(a, pi);
    root->right = CreatTree(a, pi);
    return root;
}
void inorder(BTnode* root)
{
    if (root == NULL)
    {
        return;
    }
    inorder(root->left);
    printf("%c", root->val);
    inorder(root->right);
}
int main()
{
    char a[100];
    scanf("%s", a);
    int i = 0;
    BTnode* root = CreatTree(a, &i);
    inorder(root);
    return 0;
}